/*
 *  frontend.cpp
 *  VMF
 *
 *  Created by bdm on 6/24/10.
 *  Copyright 2010 Rochester Institute of Technology. All rights reserved.
 *
 */

#include "frontend.h"


using namespace std;

// main
int main( int argc, char** argv, char** env ) {
    set<string> candidates;
    ElectionRegistry registry;

    //TODO: Determine where to put the following code chunk:
    registry.add( string("Borda"), new Creator<Borda>() );
    registry.add( string("Plurality"), new Creator<Plurality>() );
    registry.add( string("Veto"), new Creator<Veto>() );
    registry.add( string("Condorcet"), new Creator<CondorcetElection>() );
    registry.add( string("Copeland"), new Creator<CopelandElection>() );
    registry.add( string("Countdown"), new Creator<Countdown>() );
    registry.add( string("Scoring Vector"), new Creator<ScoringVector>() );
    //END TODO
    cout << "How many candidates are in the election? ";
    int count;
    cin >> count;
    if( count <= 1 || !cin ) { 
        cerr << "Error, enter a number >= 1.\n";
        exit(1);
    }
    cout << "Enter a candidate's name, hit enter. Do this " << count << " time(s).\n";
    string in;
    while( count-- > 0 ) {
        cin >> in;
        if( !cin.good() ) {
            ++count;
            cin.clear();
            cin.sync();
            //ERROR CONDITION
        } else {
            int initial = candidates.size();
            candidates.insert( in );
            int final = candidates.size();
            if( final != initial + 1 ) {
                //the user attempted to create two candidates of the same name...
                ++count;
            }
        }
    }
    if( !cin.good() ) {
        count++;
        //Error condition
        cin.clear();
        cin.sync();
    }
 
    if( candidates.size() < 2 ) {
        cerr << "ERROR: At least two candidates needed for an election.\n";
        exit(1);
    }
    ElectionBase* e = new Borda( candidates );
    unsigned char c = 0;
    while( c != 'q' && c != 'Q' ) {
        cout << "\nWhat would you like to do?\n" << 
            "\t1. Add Vote\n" <<
            "\t\tV. Add Random Votes\n" <<
            "\t2. Remove Vote\n" <<
            "\t3. List Votes\n" <<
            "\t4. Add Candidate\n" <<
            "\t5. Remove Candidate\n" <<
            "\tR. Run Election\n" <<
            "\tC. Change Election\n"; 
        if( dynamic_cast<PositionalScoreElection*>(e) ) {
            cout << "\tM. Manipulate with Greedy Algorithm\n"; 
            cout << "\tB. Run Greedy Algorithm with bounding scoring vectors.\n";
        }
        cout << "\tX. Clear the votes in the election.\n" <<
            "\tQ. Quit\n" <<
            "Enter desired option: ";
        cout.flush();
        c = single_char_input();
        cout << "\n";
        switch (c) {
            case '1':
                {
                    e->add_vote_interactive();
                }
                
                break;
            case 'V':
            case 'v':
                {
                    int n;
                    cout << "How many random votes do you want to add: ";
                    cin >> n;
                    if ( n >= 1 ) {
                        e->add_random_votes( n );
                    }
                }
                break;
            case '2':
                { 
                    
                    cout << "Votes currently in the election:\n";
                    e->print_votes();
                    if( e->remove_vote_interactive() ) {
                        cout << "Vote successfully removed.\n";
                    }
                    else {
                        cerr << "ERROR: Vote could not be removed.\n";
                    }
                }
                break;
            case '3':
                {
                    cout << "Votes currently in the election:\n";
                    e->print_votes();
                }
                break;
            case '4': 
                cout << "Enter the name of a candidate previously removed from the election: ";
                cout.flush();
                cin >> in;
                e->add_candidate( in );
                break;
            case '5':
                cout << "Enter the name of a candidate in the election to remove them or anything else to go back: ";
                cout.flush();
                cin >> in;
                e->remove_candidate( in );
                break;
            case 'R':
            case 'r':
                cout << e->run_election() << endl;
                break;
            case 'C':
            case 'c':
                {
                    cout << "Which election type would you like to change the election to?\n";
                    //cout << "\t1. Plurality\n\t2. Veto\n\t3. Borda\n\t4. (n,n-1,...,1,0,...,0)\n\t5. (a1,a2,...,an,0,...,0)\n\t6. Condorcet\n\t7. Copeland\n";
                   multiset<RationalVote> rv;
                    multiset<IrrationalVote> iv;
                    if( dynamic_cast<RationalElection*>(e) ) { 
                        rv = dynamic_cast<RationalElection*>(e)->get_votes();
                    } else if( dynamic_cast<IrrationalElection*>(e) ) {
                        iv = dynamic_cast<IrrationalElection*>(e)->get_votes();
                    }
                    
                    map<int,string> key_assoc;
                    set<string> keys = registry.get_names();
                    int n = 1;
                    set<string>::iterator i = keys.begin();
                    while( i != keys.end() ) {
                        key_assoc[n++] = *(i++);
                    }

                    for_each( key_assoc.begin(), key_assoc.end(), map_print<int,string> );
                     cout << "Enter the number corresponding to the desired election:\n";
                    //TODO: Error check input
                    stringstream ss;
                    if( registry.size() < 10 ) { 
                        ss << single_char_input();
                    }
                    else {
                        // TODO: Error check.
                        cin >> in;
                        ss << in;
                    }

                    ss >> n;

                    ElectionBase* e2 = registry.create( key_assoc[n], candidates );
                    if( e2 ) {
                        delete e;
                        e = e2;
                        if( dynamic_cast<IrrationalElection*>(e) ) { 
                            multiset<IrrationalVote>::iterator v = iv.begin();
                            while( v != iv.end() ) {
                                dynamic_cast<IrrationalElection*>(e)->add_vote( *v );
                                ++v;
                            }
                        } else if ( dynamic_cast<RationalElection*>(e) ) {
                            multiset<RationalVote>::iterator v = rv.begin();
                            while( v != rv.end() ) {
                                dynamic_cast<RationalElection*>(e)->add_vote( *v );
                                ++v;
                            }
                        }
                    }
                    else {
                        cout << "Invalid election specified.\n";
                    }
                    // TODO: Following needs to be interactive stuff
                                /*
                                cout << "Creating a new Copeland Election with tie value = " << alpha << ".\n";
                                e = new CopelandElection( candidates, iv );
                                e->count_votes();
                                break;
                            }
                        default:
                            cout << "Invalid choice, election system unchanged.";
                            break;
                    }*/
                }
                break;
            case 'M':
            case 'm':
            if ( dynamic_cast<PositionalScoreElection*> (e) )
            {
                PositionalScoreElection* p = dynamic_cast<PositionalScoreElection*> (e);
                cout << "Unique winner problem [Y/n]: ";
                cout.flush();
                // unique winner problem
                char k = single_char_input();
                cout << "\n";

                int unique = ( k != 'n' && k != 'N' );
                cout << "Would you like to limit the number of manipulators [y/N]: ";
                cout.flush();
                
                k = single_char_input();
                cout << "\n";
                unsigned int limit = 0;
                if( k == 'y' || k  == 'Y' ) {
                    while( limit < 1 ) {
                        cout << "Enter the number of manipulators: ";
                        cout.flush();
                        if( !( cin >> limit ) || limit < 1 ) {
                            cerr << "ERROR: A positive integer is needed.\n";
                            if( !cin ) {
                                cin.clear();
                                cin.sync();
                            }
                        }
                    }
                    
                }
                cout << "Enter the name of the preferred candidate: ";
                cout.flush();
                cin >> in;
                // TODO: Make this not crap out when the candidate is removed from the election.
                // TODO: make this a call to a function from map<string,funct*>
                vector<RationalVote> manipulators;
                
                if( candidates.find( in ) != candidates.end() ) {
                    // DEBUG
                    if( limit == 2 && (*p)[2] > (*p)[3] && (*p)[3] <= 1 ) {
                        cout << unique << "\n";
                        manipulators = two_manipulation_three_position( *p, in, unique );
                        if( manipulators.size() ) {
                            for_each( manipulators.begin(), manipulators.end(), linear_print<RationalVote> );
                            p->add_vote( manipulators[0] );
                            p->add_vote( manipulators[1] );
                        } else {
                            cout << "No valid manipulation exists with two manipulators.\n";
                        }
                        break;
                    }
                    // END DEBUG
                    map<string, int> scores = p->get_vote_count();
                    set<string> winners = p->get_winners();
                    // This next line is kind of messy.
                    // Basically it loops while the candidate is not in the winner set (or not the unique winner if the unique flag is set) AND
                    // if the number of manipulators is less than the limit of the manipulators if such a limit was imposed.
                    while( (winners.find( in ) == winners.end() || (unique && winners.size() > 1)) && (!limit || manipulators.size() < limit ) ) {
                        set<string> remaining( candidates );
                        remaining.erase( in );
                        vector<string> vote;
                        vote.push_back( in );
                        int position = 1;
                        map<string,int>::iterator sc = scores.begin();
                        while( p->position_score( position++ ) > 0 ) {
                            map<string,int>::iterator i = scores.begin();
                            int min = -1;
                            string target_min_candidate;
                            string target_max_candidate = "";
                            while( i != scores.end() ) {
                                if( remaining.find( i->first ) != remaining.end() ) {
                                    if( i->second < min || min == -1 ) {
                                        min = i->second;
                                        target_min_candidate = i->first;
                                    }
                                }
                                ++i;
                            }
                            vote.push_back(target_min_candidate);
                            remaining.erase( target_min_candidate );                                
                        }
                        vote.insert( vote.end(), remaining.begin(), remaining.end() );
                        p->add_vote(vote);
                        manipulators.push_back( vote );
                        scores = p->get_vote_count();
                        winners = p->get_winners();
                    }
                    cout << "Manipulation used " << manipulators.size() << " manipulators.\n";
                    cout << "Added votes:\n";
                    for_each( manipulators.begin(), manipulators.end(), linear_print<RationalVote> );
                }
                
            }
                break;
            case 'x':
            case 'X':
                cout << "Erasing all votes in the election.\n";
                e->erase_votes();
                break;
            case 'b':
            case 'B':
            {
                
                vector<unsigned int> protocol;
                PositionalScoreElection* ptr = dynamic_cast<PositionalScoreElection*> (e);
                if( !ptr )
                    break;
                
                PositionalScoreElection& p = *ptr;
                int i = 0;
                while( p[i] > 0 ) {
                    cout << p[i] << " ";
                    protocol.push_back( p[i++] );
                }
                cout << "\n";
                ScoringVector sv( p.get_candidates(), p.get_votes() );
                sv.set_scoring_vector( protocol );
                bound_test( sv );
                
                /*int vcount = 5000;
                int runs = 100;
                for( int c = 6; c <= 12; c++ ) {
                    protocol.push_back( c - 1 );
                    vector<int>::iterator k = protocol.begin();
                    cout << "Protocol: <";
                    while( k != protocol.end() ) {
                        cout << *k;
                        ++k;
                        if( k!= protocol.end() ) {
                            cout << ", ";
                        }
                    }
                    cout << ">\n";
                    for( int i = vcount / 10; i <= vcount + 1; i += vcount / 10 ) {
                        int diff = 0;
                        for( int j = 0; j < runs; j++ ) {
                            pair<int,int> p = bound_test( i, c, protocol );
                            diff += (p.second - p.first);
                            //cout << p.second << " - " << p.first << " = " <<  p.second - p.first << "; " << diff << "\n";
                            
                        }
                        cout << i << " votes, " << c << " candidates: " << "(" 
                        << (double)diff / runs 
                        //<< ", " 
                        //<< (double)sums.second / runs << ") d=" 
                        //<< (double)(sums.second - sums.first) / runs 
                        //<< " r=" << (double)sums.second / (double)sums.first 
                        << "\n";
                    }
                    cout << endl;
                }*/
                break;
            }
            default:
                break;
        }
    }
    if( e )
        delete e;
    return 0;
}

vector<RationalVote> two_manipulation_three_position( const PositionalScoreElection& e, const string& preferred, int unique ) {
    vector<RationalVote> votes;
    
    map<string,int> scores = e.get_vote_count();
    int pref = scores[preferred] + 2 * e[0];
    scores.erase(preferred);
    map<string,int>::iterator s = scores.begin();
    multiset< pair<int,string> > bins;
    while( s != scores.end() ) {
        s->second = pref - s->second;
        if( unique ) {
            s->second -= 1;
        }
        bins.insert( pair<int,string>(s->second,s->first) );
        cout << s->first << " can hold " << s->second << " points \n";
        ++s;
    }
    
    // If a negative bin exists then manipulation with 2 manipulators is impossible as
    // at least one candidate has too many points to beat.
    if( (bins.begin())->first >= 0 ){
        while( bins.size() > 4 ) {
            bins.erase( bins.begin() );
        }
    } else {
        cout << "Manipulation impossible.";
        return votes;
    }
    
    set<multiset<int> > scoring_choices;
    multiset<int> c;
    map< multiset<int>, pair< vector<int>, vector<int> > > v_map;
    pair< vector<int>, vector<int> > v_pair;
    // in all these examples bin(c4) >= bin(c3) >= bin(c2) >= bin(c1)
    
    // < a2 + a2, a3 + a3 > TESTED AND VERIFIED
    //   p > c2 > c1
    //   p > c2 > c1
    c.insert( 2 * e[2] );
    c.insert( 2 * e[1] );
    scoring_choices.insert( c );
    v_pair.first.clear();
    v_pair.second.clear();
    v_pair.first.push_back( 1 );
    v_pair.first.push_back( 0 );
    v_pair.second = v_pair.first;
    v_map[c] = v_pair;
    c.clear();
    
    // < a2 + a3, a2, a3 > TESTED AND VERIFIED
    //   p > c2 > c3
    //   p > c3 > c1
    c.insert( e[2] ); 
    c.insert( e[1] ); 
    c.insert( e[1] + e[2] );
    scoring_choices.insert( c );
    v_pair.first.clear();
    v_pair.second.clear();
    v_pair.first.push_back( 1 );
    v_pair.first.push_back( 2 );
    v_pair.second.push_back( 2 );
    v_pair.second.push_back( 0 );
    v_map[c] = v_pair;
    c.clear();
    
    // < a2, a2, a3, a3> TESTED AND VERIFIED
    //   p > c4 > c2
    //   p > c3 > c1
    c.insert( e[2] );
    c.insert( e[2] );
    c.insert( e[1] );
    c.insert( e[1] );
    scoring_choices.insert( c );
    v_pair.first.clear();
    v_pair.second.clear(); 
    v_pair.first.push_back( 3 );
    v_pair.first.push_back( 1 );
    v_pair.second.push_back( 2 );
    v_pair.second.push_back( 0 );
    v_map[c] = v_pair;
    c.clear();
    
    // < a2, a2, a3 + a3 >/<a3 + a3, a2, a2> (note that a3+a3 may be > a2) TESTED AND VERIFIED
    //  p > c3 > c1 
    //  p > c2 > c1
    // OR
    //  p > c2 > c3
    //  p > c1 > c3
    c.insert( e[1] );
    c.insert( e[1] );
    c.insert( 2 * e[2] );
    scoring_choices.insert( c );
    v_pair.first.clear();
    v_pair.second.clear();
    if( e[1] > 2 * e[2] ) {
        v_pair.first.push_back( 2 );
        v_pair.first.push_back( 0 );
        v_pair.second.push_back( 1 );
        v_pair.second.push_back( 0 );
    } else {
        v_pair.first.push_back( 1 );
        v_pair.first.push_back( 2 );
        v_pair.second.push_back( 0 );
        v_pair.second.push_back( 2 );
    }
    v_map[c] = v_pair;
    c.clear();
    
    // < a2 + a3, a2 + a3 > UNTESTED, SHOULD WORK
    // p > c1 > c2
    // p > c2 > c1
    c.insert( e[1] + e[2] );
    c.insert( e[1] + e[2] );
    scoring_choices.insert( c );
    v_pair.first.clear();
    v_pair.second.clear();
    v_pair.first.push_back( 0 );
    v_pair.first.push_back( 1 );
    v_pair.second.push_back( 1 );
    v_pair.second.push_back( 0 );
    v_map[c] = v_pair;
    c.clear();

    multiset<int> choice;
    vector<string> chosen;
    
    set<multiset<int> >::iterator i = scoring_choices.begin();
    
    while( i != scoring_choices.end() && !choice.size() ) {
        if( bins.size() >= i->size() ) {
            multiset<int>::iterator j = i->begin();
            chosen.clear();
            multiset< pair<int,string> >::iterator k = bins.begin();
            while( j != i->end() && k != bins.end() ) {
                while( *j > k->first && k != bins.end() ) {
                    ++k;
                }
                if( k != bins.end() ) {  
                    chosen.push_back( k->second );
                }
                ++j;
                if( j != i->end() ) {
                    ++k;
                }
            }
            if( k != bins.end() ) {
                choice = *i;
            }
        }
        ++i;
    }
    
    if ( !choice.size() ) {
        return votes;
    }
    
    //DEBUG
    cout << "Votes will be cast in the following way: < ";
    multiset<int>::iterator j = choice.begin();
    while( j != choice.end() ) {
        cout << *j;
        ++j;
        if( j != choice.end() ) {
            cout << ", ";
        } else {
            cout << " >\n";
        }
    }
    cout << "Corresponding candidates: ";
    vector<string>::iterator k = chosen.begin();
    while( k != chosen.end() ) {
        cout << *k;
        ++k;
        if( k != chosen.end() ) {
            cout << ", ";
        }
    }
    cout << "\n";
    //DEBUG_END
    
    vector<string> v;
    v_pair = v_map[choice];
    
    set<string> remaining = e.get_candidates();
    remaining.erase( preferred );
    v.push_back( preferred );
    v.push_back( chosen[v_pair.first[0]] );
    remaining.erase( chosen[v_pair.first[0]] );
    scores[ chosen[v_pair.first[0] ] ] += e[1];
    scores[ chosen[v_pair.second[0] ] ] += e[1];
    v.push_back( chosen[v_pair.first[1]] );
    scores[ chosen[v_pair.first[1] ] ] += e[2];
    scores[ chosen[v_pair.second[1] ] ] += e[2];
    remaining.erase( chosen[v_pair.first[1]] );
    // TODO: Make next line rank from lowest score(highest bin) to highest score(lowest bin)
    // ignoring the candidates in the other vote.
    set<string>::iterator r = remaining.begin();
    string min;
    int min_score = 0;
    while( remaining.size() ) {
        r = remaining.begin();
        min = *r;
        min_score = 0;
        while( r != remaining.end() ) {
            if( ( scores[*r] < scores[min] || !min_score ) ) {
                min = *r;
                min_score = scores[min];
            }
            ++r;
        }
        scores[min] += e[v.size()];
        remaining.erase( min );
        v.push_back( min );
    }
   
    votes.push_back( RationalVote( v ) );
    v.clear();
    
    remaining = e.get_candidates();
    remaining.erase( preferred );
    v.push_back( preferred );
    v.push_back( chosen[v_pair.second[0]] );
    remaining.erase( chosen[v_pair.second[0]] );
    v.push_back( chosen[v_pair.second[1]] );
    remaining.erase( chosen[v_pair.second[1]] );
    r = remaining.begin();
    while( remaining.size() ) {
        r = remaining.begin();
        min = *r;
        min_score = 0;
        while( r != remaining.end() ) {
            if( ( scores[*r] > scores[min] || !min_score ) ) {
                min = *r;
                min_score = scores[min];
            }
            ++r;
        }
        scores[min] += e[v.size()];
        remaining.erase( min );
        v.push_back( min );
    }
    
    votes.push_back( RationalVote( v ) );
    
    map<string,int>::iterator m = scores.begin();
    int max_score = 0;
    
    while( m != scores.end() ) {
        if( m->second > max_score ) {
            max_score = m->second;
        }
        ++m;
    }
    
    // Votes have been optimally cast, check to see if the preferred candidate
    // actually won...
    if( pref > max_score || ( !unique && pref == max_score ) ) { 
        return votes;
    } else {
        return vector<RationalVote>();
    }
}

pair<int,int> bound_test( const ScoringVector& e, vector< vector<unsigned int> > protocols ) {
    pair<unsigned int,unsigned int> ret_val(0,0);
    vector<unsigned int> scoring_protocol = e.get_scoring_vector();
    
    if( !protocols.size() ) { 
        for( unsigned int i = 0; i < scoring_protocol.size(); ++i ) {
            vector<unsigned int> p;
            p.push_back( scoring_protocol[0] );
            for( unsigned int j = 0; j < i; ++j ) {
                p.push_back( scoring_protocol[i] );
            }
            protocols.push_back( p );
        }
    }
    
    string preferred = *(e.get_candidates().begin());
    map<string,int> scores = e.get_vote_count();
    protocols.push_back( scoring_protocol );
    vector< vector<unsigned int> >::iterator i = protocols.begin();
    cout << "Running greedy algorithm on the following election:\n";
    map<string,int>::iterator s = scores.begin();
    while( s != scores.end() ) {
        if( scores[preferred] > s->second ) {
            preferred = s->first;
        }
        cout << s->first << ": " << s->second << "\n";
        ++s;
    }
    while( i != protocols.end() ) {
        map<string,int> new_scores = scores;
        vector<RationalVote> votes;
        int max = 0;
        while( new_scores[preferred] <= max || !max ) {
            vector<string> vote;
            set< pair<int,string> > sort;
            s = new_scores.begin();
            while( s != new_scores.end() ) {
                if( s->first != preferred ) {
                    sort.insert( pair<int,string>(s->second, s->first) );
                }
                ++s;
            }
            vote.push_back(preferred);
            set< pair<int,string> >::iterator p = sort.begin();
            while( p != sort.end() ) {
                vote.push_back( p->second );
                ++p;
            }
            vector<string>::iterator v = vote.begin();
            vector<unsigned int>::iterator j = i->begin();
            while( j != i->end() && v != vote.end() ) {
                new_scores[*v] += *j;
                if( *v != preferred && max < new_scores[*v] ) {
                    max = new_scores[*v];
                }
                ++j;
                ++v;
            }
            s = new_scores.begin();
            while( s != new_scores.end() ) {
                if( s->first != preferred && max < s->second ) {
                    max = s->second;
                }
                ++s;
            }
            votes.push_back( RationalVote(vote) );
        }
        // OUTPUT ONLY SECTION
        cout << "Scoring protocol: < ";
        vector<unsigned int>::iterator j = i->begin();
        while( j != i->end() ) {
            cout << *j << ", ";
            ++j;
        }
        cout << "0, ..., 0 >\n";
        cout << "Manipulation took " << votes.size() << " votes:\n";

        for_each( votes.begin(), votes.end(), linear_print<RationalVote> );
        s = new_scores.begin();
        cout << "Final scores:\n";
        while( s != new_scores.end() ) {
            cout << s->first << ": " << s->second << "\n";
            ++s;
        }
        
        cout << endl;
        //OOS END
        ++i;
        if( votes.size() > ret_val.first && i != protocols.end() ) {
            ret_val.first = votes.size();
        } else if( i == protocols.end() ) {
            ret_val.second = votes.size();
        }
    }
    
    return ret_val;
}

pair<int,int> bound_test( const unsigned int& num_votes, const unsigned int& num_candidates, const vector<unsigned int>& scoring_protocol, const vector< vector<unsigned int> >& protocols ) {
    set<string> candidates;
    for( unsigned int i = 0; i < num_candidates; ++i ) {
        string s;
        s += (char)(65 + i);
        candidates.insert( s );
    }
    
    ScoringVector e( candidates );
    e.set_scoring_vector( scoring_protocol );
    vector<RationalVote> votes;
    for( unsigned int i = 0; i < num_votes; i++ ) {
        vector<string> remaining( candidates.begin(), candidates.end() );
        vector<string> vote;
        while( remaining.size() ) {
            int index = rand() % remaining.size();
            vote.push_back( *(remaining.begin() + index) );
            remaining.erase( remaining.begin() + index );
        }
        votes.push_back( vote );
    }
    //cout << "The following votes were added to the election:\n";
    vector<RationalVote>::iterator v = votes.begin();
    while ( v != votes.end() ) { 
        e.add_vote( *v );
        ++v;
    }
    
    return bound_test( e, protocols );
}

